import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class MedianFinder {

    /** initialize your data structure here. */
    PriorityQueue<Integer> maxHeap;
    PriorityQueue<Integer> minHeap;
    public MedianFinder() {
        //初始化大根堆,维护中位数左边区间的数字
        maxHeap = new PriorityQueue<>((o1, o2)->o2-o1);
        //初始化小根堆,维护中位数右边区间的数字
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        int m = maxHeap.size();
        int n = minHeap.size();
        //区间元素个数为偶数
        if(m == n){
            //num比大根堆堆顶元素更小或者两个堆元素为空直接进
            if(m == 0 || num <= maxHeap.peek()) maxHeap.offer(num);
            else{
                //num > x
                //说明num落在右边区间
                //num先入小根堆,再讲堆顶元素放入大根堆
                minHeap.offer(num);
                maxHeap.offer(minHeap.poll());
            }
        }else if(m == n + 1){
            //区间元素个数为奇数

            //num比大根堆堆顶元素更大, 放入小根堆
            if(num > maxHeap.peek()){
                minHeap.offer(num);
            }else{
                //num <= 大根堆堆顶
                //此时放入大根堆之后元素个数m = n + 2了
                //需要再将大根堆堆顶元素放入小根堆堆顶
                maxHeap.offer(num);
                minHeap.offer(maxHeap.poll());
            }
        }
    }

    public double findMedian() {
        return maxHeap.size() > minHeap.size() ? (double)maxHeap.peek() :  ((double)(maxHeap.peek() + minHeap.peek())) / 2;
    }
}